<!DOCTYPE html>



  


<html class="theme-next muse use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">


  
  
    
    
  <script src="/lib/pace/pace.min.js?v=1.0.2"></script>
  <link href="/lib/pace/pace-theme-mac-osx.min.css?v=1.0.2" rel="stylesheet">







<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  

  

  

  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon.ico?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon.ico?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="数据结构," />










<meta name="description" content="B Tree、B+ Tree、B* TreeB+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉查找树、平衡二叉树（AVL Tree）和平衡多路查找树（B-Tree），B+树即由这些树逐步优化而来。  二叉查找树二叉树具有以下性质：">
<meta property="og:type" content="article">
<meta property="og:title" content="B Tree、B+ Tree、B* Tree">
<meta property="og:url" content="http://yoursite.com/2020/02/20/B%20Tree/index.html">
<meta property="og:site_name" content="JokerLee">
<meta property="og:description" content="B Tree、B+ Tree、B* TreeB+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉查找树、平衡二叉树（AVL Tree）和平衡多路查找树（B-Tree），B+树即由这些树逐步优化而来。  二叉查找树二叉树具有以下性质：">
<meta property="og:image" content="http://yoursite.com/2020/02/20/B%20Tree/Tree.png">
<meta property="og:image" content="http://yoursite.com/2020/02/20/B%20Tree/AVL.png">
<meta property="og:image" content="http://yoursite.com/2020/02/20/B%20Tree/AVL2.png">
<meta property="og:image" content="http://yoursite.com/2020/02/20/B%20Tree/BTree.png">
<meta property="og:image" content="http://yoursite.com/2020/02/20/B%20Tree/B+Tree.png">
<meta property="article:published_time" content="2020-02-20T09:02:14.000Z">
<meta property="article:modified_time" content="2020-02-20T10:17:39.959Z">
<meta property="article:author" content="JokerLee">
<meta property="article:tag" content="数据结构">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://yoursite.com/2020/02/20/B%20Tree/Tree.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Muse',
    version: '5.1.4',
    sidebar: {"position":"left","display":"hide","offset":12,"b2t":false,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yoursite.com/2020/02/20/B Tree/"/>






  <title>B Tree、B+ Tree、B* Tree | JokerLee</title>
  





  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?434245b8475083dafc7768fd71b61160";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




<meta name="generator" content="Hexo 4.2.0"></head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">JokerLee</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-schedule">
          <a href="/schedule/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-calendar"></i> <br />
            
            日程表
          </a>
        </li>
      
        
        <li class="menu-item menu-item-kit">
          <a href="/kit/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            百宝箱
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/02/20/B%20Tree/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="JokerLee">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JokerLee">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">B Tree、B+ Tree、B* Tree</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2020-02-20T17:02:14+08:00">
                2020-02-20
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">更新于&#58;</span>
              
              <time title="更新于" itemprop="dateModified" datetime="2020-02-20T18:17:39+08:00">
                2020-02-20
              </time>
            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E7%9F%A5%E8%AF%86%E7%82%B9/" itemprop="url" rel="index">
                    <span itemprop="name">知识点</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          
             <span id="/2020/02/20/B%20Tree/" class="leancloud_visitors" data-flag-title="B Tree、B+ Tree、B* Tree">
               <span class="post-meta-divider">|</span>
               <span class="post-meta-item-icon">
                 <i class="fa fa-eye"></i>
               </span>
               
                 <span class="post-meta-item-text">阅读次数&#58;</span>
               
                 <span class="leancloud-visitors-count"></span>
             </span>
          

          
            <span class="post-meta-divider">|</span>
            <span class="page-pv"><i class="fa fa-file-o"></i>
            <span class="busuanzi-value" id="busuanzi_value_page_pv" ></span>
            </span>
          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  2.6k
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  9
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <h1 id="B-Tree、B-Tree、B-Tree"><a href="#B-Tree、B-Tree、B-Tree" class="headerlink" title="B Tree、B+ Tree、B* Tree"></a>B Tree、B+ Tree、B* Tree</h1><h5 id="B-树索引是B-树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B-树中的B代表平（balance），而不是二叉（binary），因为B-树是从最早的平衡二叉树演化而来的。在讲B-树之前必须先了解二叉查找树、平衡二叉树（AVL-Tree）和平衡多路查找树（B-Tree），B-树即由这些树逐步优化而来。"><a href="#B-树索引是B-树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B-树中的B代表平（balance），而不是二叉（binary），因为B-树是从最早的平衡二叉树演化而来的。在讲B-树之前必须先了解二叉查找树、平衡二叉树（AVL-Tree）和平衡多路查找树（B-Tree），B-树即由这些树逐步优化而来。" class="headerlink" title="B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉查找树、平衡二叉树（AVL Tree）和平衡多路查找树（B-Tree），B+树即由这些树逐步优化而来。"></a>B+树索引是B+树在<a href="http://lib.csdn.net/base/mysql" target="_blank" rel="noopener">数据库</a>中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉查找树、平衡二叉树（AVL Tree）和平衡多路查找树（B-Tree），B+树即由这些树逐步优化而来。</h5><br>

<h1 id="二叉查找树"><a href="#二叉查找树" class="headerlink" title="二叉查找树"></a>二叉查找树</h1><h5 id="二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。"><a href="#二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。" class="headerlink" title="二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。"></a>二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。</h5><p>如下图所示是一棵平衡查找树</p>
<p><img src="/2020/02/20/B%20Tree/Tree.png" alt></p>
<p>对该二叉树的节点进行查找发现深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n，因此其平均查找次数为 (1+2+2+3+3+3) / 6 = 2.3次</p>
<p>二叉查找树可以任意地构造，同样是2,3,5,6,7,8这六个数字，也可以按照下图的方式来构造：</p>
<p><img src="/2020/02/20/B%20Tree/AVL.png" alt></p>
<p>但是这棵二叉树的查询效率就低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的，从而引出新的定义——平衡二叉树，或称AVL树。</p>
<br>

<h1 id="平衡二叉树-AVL-Tree"><a href="#平衡二叉树-AVL-Tree" class="headerlink" title="平衡二叉树 (AVL Tree)"></a>平衡二叉树 (AVL Tree)</h1><h5 id="平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差-lt-1；右边的不是AVL树，其根节点的左子树高度为3，而右子树高度为1"><a href="#平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差-lt-1；右边的不是AVL树，其根节点的左子树高度为3，而右子树高度为1" class="headerlink" title="平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差&lt;=1；右边的不是AVL树，其根节点的左子树高度为3，而右子树高度为1"></a>平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差&lt;=1；右边的不是AVL树，其根节点的左子树高度为3，而右子树高度为1</h5><p><img src="/2020/02/20/B%20Tree/AVL2.png" alt></p>
<br>

<h1 id="平衡多路查找树（B-Tree）"><a href="#平衡多路查找树（B-Tree）" class="headerlink" title="平衡多路查找树（B-Tree）"></a>平衡多路查找树（B-Tree）</h1><p><img src="/2020/02/20/B%20Tree/BTree.png" alt></p>
<p>每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。</p>
<p>模拟查找关键字29的过程：</p>
<ol>
<li>根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】</li>
<li>比较关键字29在区间（17,35），找到磁盘块1的指针P2。</li>
<li>根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】</li>
<li>比较关键字29在区间（26,30），找到磁盘块3的指针P2。</li>
<li>根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】</li>
<li>在磁盘块8中的关键字列表中找到关键字29。</li>
</ol>
<p>分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVL Tree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。</p>
<br>

<h1 id="B-Tree"><a href="#B-Tree" class="headerlink" title="B+ Tree"></a>B+ Tree</h1><p>B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。</p>
<p>从上一节中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。</p>
<p>B+Tree相对于B-Tree有几点不同：</p>
<ol>
<li>非叶子节点只存储键值信息。</li>
<li>所有叶子节点之间都有一个链指针。</li>
<li>数据记录都存放在叶子节点中。</li>
</ol>
<p>将上一节中的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：</p>
<p><img src="/2020/02/20/B%20Tree/B+Tree.png" alt></p>
<p>通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。</p>
<p>可能上面例子中只有22条数据记录，看不出B+Tree的优点，下面做一个推算：</p>
<p>InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。</p>
<p>实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2<del>4层。<a href="http://lib.csdn.net/base/mysql" target="_blank" rel="noopener">mysql</a>的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1</del>3次磁盘I/O操作。</p>
<p>数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary  index）。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。</p>
<br>

<h1 id="B-Tree-1"><a href="#B-Tree-1" class="headerlink" title="B* Tree"></a>B* Tree</h1><h5 id="是B-树的变体，在B-树的非根和非叶子结点再增加指向兄弟的指针"><a href="#是B-树的变体，在B-树的非根和非叶子结点再增加指向兄弟的指针" class="headerlink" title="是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针"></a>是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针</h5><h5 id="B-树分配新结点的概率比B-树要低，空间使用率更高"><a href="#B-树分配新结点的概率比B-树要低，空间使用率更高" class="headerlink" title="B*树分配新结点的概率比B+树要低，空间使用率更高"></a>B*树分配新结点的概率比B+树要低，空间使用率更高</h5><br>



<hr>
<h2 id="B树和B-树的区别"><a href="#B树和B-树的区别" class="headerlink" title="B树和B+树的区别"></a>B树和B+树的区别</h2><p>这都是由于B+树和B具有这不同的存储结构所造成的区别，以一个m阶树为例。</p>
<ol>
<li>关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是其只拥有m-1个关键字。【注：此处有争议，B+树到底是与B 树n-1个关键字有n棵子树保持一致，还是B+树n个关键字的结点中含有n棵子树；两种定义都可以，只要自己实现的时候统一用一种就行】。</li>
<li>存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。而且B+树叶子结点上还存储了指向与该结点相邻的后一个叶子结点的指针信息，这主要是为了加快检索多个相邻叶子结点的效率考虑。</li>
<li>分支结点的构造不同；分支结点并不存储真正的信息，仅包含着索引信息，其保存着叶子节点的最小值作为索引及其儿子指针（指的是磁盘块的偏移量）。【注：此处有争议，是以最大值还是最小值作为索引看个人实现】。</li>
<li>查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。</li>
<li>用处不用：由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引，而B树则常用于文件索引</li>
</ol>
<h2 id="为什么说B-树比B-树更适合实际应用中操作系统的文件索引和数据库索引？"><a href="#为什么说B-树比B-树更适合实际应用中操作系统的文件索引和数据库索引？" class="headerlink" title="为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？"></a>为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？</h2><p>1) B+树的磁盘读写代价更低<br>　　B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。<br>2) B+树的查询效率更加稳定<br>　　由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。 </p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag"># 数据结构</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2020/02/19/%E5%8D%95%E4%BE%8B%E6%A8%A1%E5%BC%8F/" rel="next" title="单例模式">
                <i class="fa fa-chevron-left"></i> 单例模式
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2020/02/20/ACID%E4%BA%8B%E5%8A%A1/" rel="prev" title="ACID&事务隔离级别">
                ACID&事务隔离级别 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">JokerLee</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/%7C%7C%20archive">
              
                  <span class="site-state-item-count">5</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">2</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">4</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/jokerLeee" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="mailto:745965645@qq.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#B-Tree、B-Tree、B-Tree"><span class="nav-number">1.</span> <span class="nav-text">B Tree、B+ Tree、B* Tree</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#B-树索引是B-树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B-树中的B代表平（balance），而不是二叉（binary），因为B-树是从最早的平衡二叉树演化而来的。在讲B-树之前必须先了解二叉查找树、平衡二叉树（AVL-Tree）和平衡多路查找树（B-Tree），B-树即由这些树逐步优化而来。"><span class="nav-number">1.0.0.0.1.</span> <span class="nav-text">B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉查找树、平衡二叉树（AVL Tree）和平衡多路查找树（B-Tree），B+树即由这些树逐步优化而来。</span></a></li></ol></li></ol></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#二叉查找树"><span class="nav-number">2.</span> <span class="nav-text">二叉查找树</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。"><span class="nav-number">2.0.0.0.1.</span> <span class="nav-text">二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。</span></a></li></ol></li></ol></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#平衡二叉树-AVL-Tree"><span class="nav-number">3.</span> <span class="nav-text">平衡二叉树 (AVL Tree)</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差-lt-1；右边的不是AVL树，其根节点的左子树高度为3，而右子树高度为1"><span class="nav-number">3.0.0.0.1.</span> <span class="nav-text">平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差&lt;&#x3D;1；右边的不是AVL树，其根节点的左子树高度为3，而右子树高度为1</span></a></li></ol></li></ol></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#平衡多路查找树（B-Tree）"><span class="nav-number">4.</span> <span class="nav-text">平衡多路查找树（B-Tree）</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#B-Tree"><span class="nav-number">5.</span> <span class="nav-text">B+ Tree</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#B-Tree-1"><span class="nav-number">6.</span> <span class="nav-text">B* Tree</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#是B-树的变体，在B-树的非根和非叶子结点再增加指向兄弟的指针"><span class="nav-number">6.0.0.0.1.</span> <span class="nav-text">是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#B-树分配新结点的概率比B-树要低，空间使用率更高"><span class="nav-number">6.0.0.0.2.</span> <span class="nav-text">B*树分配新结点的概率比B+树要低，空间使用率更高</span></a></li></ol></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#B树和B-树的区别"><span class="nav-number">6.1.</span> <span class="nav-text">B树和B+树的区别</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#为什么说B-树比B-树更适合实际应用中操作系统的文件索引和数据库索引？"><span class="nav-number">6.2.</span> <span class="nav-text">为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">JokerLee</span>

  
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-area-chart"></i>
    </span>
    
      <span class="post-meta-item-text">本站总字数&#58;</span>
    
    <span title="本站总字数">5.3k</span>
  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Muse</a></div>




        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

  
    <span class="site-uv">
      <i class="fa fa-user"></i>&nbsp;&nbsp;&nbsp;本站访客数
      <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
      次
    </span>
  

  
    <span class="site-pv">
      <i class="fa fa-eye"></i>&nbsp;&nbsp;&nbsp;本站访问数
      <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
      次
    </span>
  
</div>





  <script type="text/javascript">
    (function() {
      var hm = document.createElement("script");
      hm.src = "//tajs.qq.com/stats?sId=66520966";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
          <span id="scrollpercent"><span>0</span>%</span>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  


  











  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  

  
  
    <script type="text/javascript" src="/lib/canvas-nest/canvas-nest.min.js"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  

  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  
  <script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.4.js"></script>
  <script>AV.initialize("CDRocj9P5t8f77lE70CFvaC2-gzGzoHsz", "mHWzbxsbaVRQb7BnOyT9y5A8");</script>
  <script>
    function showTime(Counter) {
      var query = new AV.Query(Counter);
      var entries = [];
      var $visitors = $(".leancloud_visitors");

      $visitors.each(function () {
        entries.push( $(this).attr("id").trim() );
      });

      query.containedIn('url', entries);
      query.find()
        .done(function (results) {
          var COUNT_CONTAINER_REF = '.leancloud-visitors-count';

          if (results.length === 0) {
            $visitors.find(COUNT_CONTAINER_REF).text(0);
            return;
          }

          for (var i = 0; i < results.length; i++) {
            var item = results[i];
            var url = item.get('url');
            var time = item.get('time');
            var element = document.getElementById(url);

            $(element).find(COUNT_CONTAINER_REF).text(time);
          }
          for(var i = 0; i < entries.length; i++) {
            var url = entries[i];
            var element = document.getElementById(url);
            var countSpan = $(element).find(COUNT_CONTAINER_REF);
            if( countSpan.text() == '') {
              countSpan.text(0);
            }
          }
        })
        .fail(function (object, error) {
          console.log("Error: " + error.code + " " + error.message);
        });
    }

    function addCount(Counter) {
      var $visitors = $(".leancloud_visitors");
      var url = $visitors.attr('id').trim();
      var title = $visitors.attr('data-flag-title').trim();
      var query = new AV.Query(Counter);

      query.equalTo("url", url);
      query.find({
        success: function(results) {
          if (results.length > 0) {
            var counter = results[0];
            counter.fetchWhenSave(true);
            counter.increment("time");
            counter.save(null, {
              success: function(counter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(counter.get('time'));
              },
              error: function(counter, error) {
                console.log('Failed to save Visitor num, with error message: ' + error.message);
              }
            });
          } else {
            var newcounter = new Counter();
            /* Set ACL */
            var acl = new AV.ACL();
            acl.setPublicReadAccess(true);
            acl.setPublicWriteAccess(true);
            newcounter.setACL(acl);
            /* End Set ACL */
            newcounter.set("title", title);
            newcounter.set("url", url);
            newcounter.set("time", 1);
            newcounter.save(null, {
              success: function(newcounter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(newcounter.get('time'));
              },
              error: function(newcounter, error) {
                console.log('Failed to create');
              }
            });
          }
        },
        error: function(error) {
          console.log('Error:' + error.code + " " + error.message);
        }
      });
    }

    $(function() {
      var Counter = AV.Object.extend("Counter");
      if ($('.leancloud_visitors').length == 1) {
        addCount(Counter);
      } else if ($('.post-title-link').length > 1) {
        showTime(Counter);
      }
    });
  </script>



  

  

  
  

  

  

  

</body>
</html>
<!-- ҳ����С���� -->
<script type="text/javascript" src="/js/src/love.js"></script>
